﻿using System;
using System.Numerics;

namespace OmniKits
{
    using Utility = Utilities.MathUtility;

    partial class Helpers
    {
        public sealed class MathHelper { }
        public static MathHelper MathEx { get; } 

        public static int GreatestCommonDivisor(this MathHelper _, int a, int b)
            => Utility.GreatestCommonDivisor(a, b);
        public static long GreatestCommonDivisor(this MathHelper _, long a, long b)
            => Utility.GreatestCommonDivisor(a, b);
        public static BigInteger GreatestCommonDivisor(this MathHelper _, BigInteger a, BigInteger b)
            => Utility.GreatestCommonDivisor(a, b);
    }
}

namespace OmniKits.Utilities
{
    public static class MathUtility
    {
#pragma warning disable 1591

        #region Stein GCD

        #region int
        public static int GreatestCommonDivisor(int a, int b)
        {
            if (a < 0 || b < 0)
                throw new ArgumentOutOfRangeException();

            if (a > b)
                return SteinGcdNoCheck(a, b);
            else
                return SteinGcdNoCheck(b, a);
        }
        private static int SteinGcdNoCheck(int a, int b)
        {
            if (b == 0)
                return a;

            if (a % 2 == 0 && b % 2 == 0)
                return SteinGcdNoCheck(a / 2, b / 2) * 2;

            if (a % 2 == 0)
                return SteinGcdNoCheck(a / 2, b);

            if (b % 2 == 0)
                return SteinGcdNoCheck(a, b / 2);

            return SteinGcdNoCheck((a + b) / 2, (a - b) / 2);
        }
        #endregion

        #region long
        public static long GreatestCommonDivisor(long a, long b)
        {
            if (a < 0 || b < 0)
                throw new ArgumentOutOfRangeException();

            if (a > b)
                return SteinGcdNoCheck(a, b);
            else
                return SteinGcdNoCheck(b, a);
        }
        private static long SteinGcdNoCheck(long a, long b)
        {
            if (b == 0)
                return a;

            if (a % 2 == 0 && b % 2 == 0)
                return SteinGcdNoCheck(a / 2, b / 2) * 2;

            if (a % 2 == 0)
                return SteinGcdNoCheck(a / 2, b);

            if (b % 2 == 0)
                return SteinGcdNoCheck(a, b / 2);

            return SteinGcdNoCheck((a + b) / 2, (a - b) / 2);
        }
        #endregion

        #region BigInteger
        public static BigInteger GreatestCommonDivisor(BigInteger a, BigInteger b)
        {
            if (a < 0 || b < 0)
                throw new ArgumentOutOfRangeException();

            if (a > b)
                return SteinGcdNoCheck(a, b);
            else
                return SteinGcdNoCheck(b, a);
        }
        private static BigInteger SteinGcdNoCheck(BigInteger a, BigInteger b)
        {
            if (b == 0)
                return a;

            if (a % 2 == 0 && b % 2 == 0)
                return SteinGcdNoCheck(a / 2, b / 2) * 2;

            if (a % 2 == 0)
                return SteinGcdNoCheck(a / 2, b);

            if (b % 2 == 0)
                return SteinGcdNoCheck(a, b / 2);

            return SteinGcdNoCheck((a + b) / 2, (a - b) / 2);
        }
        #endregion

        #endregion
    }
}
